Out: Monday, October 24, 2016.
Due: Monday, October 31, 2016 at 600pm local time.
Update 1: Numbered rules and added rule 3.3 (Mon Oct 24 18:47:58 2016)
Update 2: Added make-turn-left, etc. to deliverables. (Wed Oct 26 16:56:46 2016)
Update 3: Fixed bug in example for f2. (Wed Oct 26 23:04:38 2016)
Update 4: Clarified rule for spaces between arguments in Rule 3.1 (Thu Oct 27 14:44:36 2016)
The goal of this problem set is to give you practice using context arguments and invariants.
Remember that you must follow the design recipe, and write invariants (as WHERE clauses) whenever an argument represents context information.
You must use DrScheme's HtDP Intermediate Student Language with Lambda. Use list abstractions like filter, fold, and map whenever they are helpful. As before, you will be penalized for failing to use these when they are "obviously" applicable.
Note: not everything on this problem set requires the use of invariants; some may only require generalization. Part of your task is to figure out when you need an invariant and when you do not. Remember, it is the purpose statement that determines whether or not you need to state an invariant.
The quality of your purpose statements, invariants, and halting measures will be an important part of the evaluation of your submission.
Remember that you must follow the design recipe. Your deliverables include the data definitions (including interpretation and templates), contract and purpose header, strategies, code, and tests. Be sure to sync your work and fill out a Work Session Report at the end of every work session. Use the Work Session Report for PS07.
As usual, the rubric for grading is here.
Recall that the syntax-tree representation of GarterSnake is defined as follows:
;; A Program is a ListOfDefinition. (define-struct def (name args body)) ;; A Definition is a (make-def Variable ListOfVariable Exp) ;; INTERPRETATION: ;; name is the name of the function being defined ;; args is the list of arguments of the function ;; body is the body of the function. (define-struct varexp (name)) (define-struct appexp (fn args)) ;; An Exp is one of ;; -- (make-varexp Variable) ;; -- (make-appexp Variable ListOfExp) ;; INTERPRETATION; ;; (make-varexp v) represents a use of the variable v ;; (make-appexp f (list e1 ... en)) represents a call to the function ;; named f, with arguments e1,..,en ;; A Variable is a Symbol.
Your task is to write
;; program-to-strings : Program PosInt -> ListOfString ;; GIVEN: GarterSnake program and a width ;; RETURNS: a representation of the program as a sequence of lines, ;; following the formatting rules described below.
The detailed formatting rules will be given below, but here's an example of the function:
(define sample-program
(list
(make-def 'a-very-long-function-name
(list 'x)
(make-appexp 'f1 (list (make-varexp 'x))))
(make-def 'f2 (list 'x 'a-very-long-variable-name 'y)
(make-appexp 'f1 (list (make-varexp 'y))))
(make-def 'f3 (list 'x 'z 't 'u)
(make-appexp
'f1
(list (make-appexp
'f2 (list (make-varexp 'z)
(make-varexp 'y)))
(make-varexp 'z)
(make-appexp
'f1 (list (make-appexp
'f2 (list (make-varexp 'z)
(make-varexp 'y)))
(make-varexp 'z))))))))
(program-to-strings sample-program 20)
=>
(list
"def a-very-long-function-name (x) :"
" f1(x)"
"def f2 (x,"
" a-very-long-variable-name,"
" y) :"
" f1(y)"
"def f3 (x,z,t,u) :"
" f1(f2(z, y),"
" z,"
" f1(f2(z, y),"
" z))")
The formatting rules are as follows:
1. Layout of Programs:
The program is formatted by formatting each of definitions in
sequence.
2. Layout of Definitions:
2.1 Definitions are formatted by formatting the header, consisting of
the function name and arguments, followed by the function body,
starting on a new line with 4 additional spaces of indentation.
2.2 The function is header is formatted as
def fnname (arg1,arg2,arg3) :
if it will fit on a line no longer than the given width.
2.3 If the function header as shown in 2.2 will not fit into the given
width, then the function header should be laid out as
def fnname (arg1,
arg2,
..
argn) :
with each subsequent argument indented to line up under the first
argument.
3. Layout of Expressions:
3.1 For a function application, if the string
fnname(e1, e2, e3)
will fit on a single line, including its indentation and closing
parentheses (and comma if needed), then it is formatted that way.
3.2 If a function application, including its indentation, closing
parentheses and comma (if present), will not fit on a single line, but
the
fnname(e1,
will fit, then that much of the call is placed on a single line and
each of the remaining argument expressions begins on a separate line,
indented to line up under e1, and the closing parenthesis is placed on
the same line as the last argument expression. e.g.
foo(e1,
e2,
e3)
The closing paren is always on the last line. Here "e2,", etc.
stand for a set of lines with a comma at the end of the last line,
and "e2)" stand for a set of lines with a right parenthesis at the
end of the last line.
3.3 If
fnname(e1,
including its indentation, closing parentheses and comma, will not fit
on a single line, then the function name is placed on a line by
itself, and e1 is formatted beginning on the next line, indented with
1 additional space and a left parenthesis. Subsequent arguments are
indented to line up under e1, e.g.
fnname
(e1,
e2,
..
en)
Here "e2,", etc., stands for a set of lines with a comma at the end of
the last line, and "e2)", etc., stands for a set of lines with a right
parenthesis at the end of the last line.
3.4 If the expression is a variable, then it is placed on a line by
itself with its associated indentation, right parentheses and possible
comma even if that does not fit on one line.
4. General Properties
These properties all follow from the rules above, but are stated here
for reference.
4.1 There are no blank lines.
4.2 No line ever ends with a space.
4.3 No left parenthesis is ever followed by a space, and no left
parenthesis ever appears at the end of a line.
4.4 No right parenthesis is ever preceded by a space or a comma, and
no right parenthesis ever appears at the start of a line.
4.4 For any given program and width, these rules determine one and only
one layout.
4.5 Following these rules may result in some lines that are longer
than the given width. For example, the name binary-search-helper-2
(besides being a poor function name!) will never fit within a line of
length 10.
To help you debug your program, we have provided in extras.rkt the function:
;; display-strings! : ListOfString -> Void ;; GIVEN: a list of strings ;; EFFECT: displays the strings on separate lines ;; RETURNS: no valueHere is a sample interaction:
> (display-strings!
(cons "12345678901234567890"
(program-to-strings sample-program 20)))
12345678901234567890
def a-very-long-function-name (x) :
f1(x)
def f2 (x,
a-very-long-variable-name,
y) :
f1(y)
def f3 (x,z,t,u) :
f1(f2(z, y),
z,
f1(f2(z, y),
z))
>
Turn in your solution is a file named q1.rkt. You also must turn in a call graph for your solution, as in the last few problem sets. Call this file call-graph-1 with an appropriate suffix. Be sure your code includes a halting measure for every function that appears in a cycle in your call graph.
This problem requires careful analysis of the context. For example, when your program generates the string
" f1(f2(z, y),"what information does it need to know about the context? If there is more than one thing that it needs to know, you can introduce multiple context variables to keep track of them.
A Program is a ListOfInstruction
Interp: A sequence of instructions, to be executed from left to
right.
An Instruction is one of
-- (make-turn-left) Interp: a turn-left instruction
-- (make-turn-right) Interp: a turn-right instruction
-- (make-move-forward PosInt) Interp: an instruction to move forward
the given number of steps.
Thus, if the robot is facing east at x=20, then after a (make-move-forward 10) instruction, it will end still facing east, with its x-coordinate in the interval [28,32] (that is, 30 plus or minus 2), and its y-coordinate unchanged. If the instruction were instead (make-move-forward 1), then afterwards the x coordinate would be in the interval [20,23] (not [19,23]).
You are to write file named q2.rkt that provides the following function:
;; probe-possible-outcome? : Int Int Program Int Int -> Bool ;; GIVEN: starting coordinates x0, y0, a robot program p, and ending ;; coordinates x1, y1. ;; RETURNS: true iff the robot, starting at (x0, y0) and facing north, ;; and executing program p according to the tolerances given above, ;; could end at (x1, y1). ;; EXAMPLES: ;; Let p1 = (list (make-turn-right) ;; (make-move-forward 10) ;; (make-turn-right) ;; (make-move-forward 5)) ;; then (probe-possible-outcome 20 100 p1 x1 y1) = true iff ;; x1 is in the interval [28, 32] and y1 is in the interval ;; [103,107]. ;; make-turn-right : -> Instruction ;; make-turn-left : -> Instruction ;; make-move-forward : PosInt -> Instruction ;; As usual, if these are defined by define-struct, you need not ;; write any of the other deliverables (purpose statement, tests, etc.)
For this problem, your program needs to provide acceptable performance. "Acceptable" means that it can provide answers for programs of length 20 in a few seconds-- the time it takes to take a sip of coffee. If you are tempted to go get a fresh cup of coffee, your program is too slow. HINT: Small changes in your code will probably not help. You will need to devise a good representation for the possible states of the robot in the middle of the program execution.
Last modified: Thu Oct 27 14:44:38 Eastern Daylight Time 2016